#ifndef CASAMENTOAPROXIMADO_H_
#define CASAMENTOAPROXIMADO_H_
#include <string>
#include <iostream>
using std::cout;
using std::endl;
using std::string;
namespace casamento {
        class CasamentoAproximado {
                private: 
                        static const int maxChar;
                public:
                        static void shiftAndAproximado (string T,int n,string P,int m, int k);
        };
        
        const int CasamentoAproximado::maxChar = 256;
        void CasamentoAproximado:: shiftAndAproximado (string T,int n, string P,
                                                 int m, int k) {                                                        
                // @{\it Pr\'e-processamento do padr\~ao}@
                int *R = new int[k+1];
                int *M = new int[maxChar];
                for (int i = 0; i < maxChar; i++) 
                        M[i] = 0;
                for (int j = 0; j < m; j++) 
                        M[(unsigned char)P[j]] = M[(unsigned char)P[j]] | (1 << (m-j-1));
    
                // @{\it Pesquisa}@
                int Ri =  1 << (m-1); 
                R[0] = 0;
                for (int j = 1; j <= k; j++) 
                        R[j] = (1 << (m-j)) | R[j-1];
                for (int i = 0; i < n; i++) {
                        int Rant = R[0];
                        int RNovo = ((Rant >> 1) | Ri) & M[(unsigned char)T[i]];
                        R[0] = RNovo;
                        for (int j = 1; j <= k; j++) {
                                RNovo = ((R[j] >> 1) & M[(unsigned char)T[i]]) | Rant | ((Rant | RNovo) >> 1);
                                Rant = R[j];
                                R[j] = RNovo | Ri;
                        }      
                        
                        if ((RNovo & 1) != 0) 
                                cout << "Casamento na posicao: " << T[i] << endl;  
                }
                delete [] R; delete [] M;
        }       
}
#endif
